The present invention generally relates to image convolution techniques and, in particular, to performing convolutions of digital images or object-based graphics in a scan line rendering environment.
Current image convolution systems perform image convolutions using semiconductor memory frame buffers. However, this has the potential of limiting the size of an image on which convolutions can be applied to what can be stored in available memory, especially where high speed rendering of an image is required. Further, current systems allow convolutions to be applied only to images formed of pixel-based image data, and not in general to images formed from object-based graphic image data.
With reference to FIG. 1, a convolution of an image with an arbitrary mathematical function can be defined as follows. An image 10 can be denoted by a function I(x,y) where x is a position horizontally along a scan line 11 and y is a position vertically down the image 10 from the top left hand corner of the image 10. A pixel 12 with pixel integer coordinates p and q has a value returned by the function I(x,y) in the region pxe2x89xa6xxe2x89xa6p+1, qxe2x89xa6y+1. In practice, an image is usually represented as a series of colour components, for example, red, green and blue known as RGB-values. Thus, I(x,y) usually denotes several functions, one for each colour component, IR(x,y), IG(x,y) and IB(x,y). The convolution of the image 10 with a predetermined function f(x,y) is mathematically defined as                                           I            ⊗            f                    =                                    ∫                              -                ∞                            ∞                        ⁢                                          ∫                                  -                  ∞                                ∞                            ⁢                                                I                  ⁡                                      (                                          u                      ,                      v                                        )                                                  ⁢                                  f                  ⁡                                      (                                                                  x                        -                        u                                            ,                                              y                        -                        v                                                              )                                                  ⁢                                  xe2x80x83                                ⁢                                  ⅆ                  u                                ⁢                                  ⅆ                  v                                                                    ,                            (                  EQ          ⁢                      xe2x80x83                    ⁢          1                )            
where, in theory, f can be defined over any finite or infinite domain. In practical terms, a convolution is usually performed by representing f(x,y) by a finite mask 21 (also known as a kernel) kij, i=xe2x88x92m, . . . , m, j=xe2x88x92n, . . . , n shown in FIG. 2 and represented so that the centre element, or coefficient of the mask, is the k00 element 22. The convolution is calculated at each pixel (p,q) as                                           ∑                          i              =                              -                m                                                    +              m                                ⁢                      xe2x80x83                    ⁢                                    ∑                              j                =                                  -                  n                                                            +                n                                      ⁢                          xe2x80x83                        ⁢                                          I                ⁡                                  (                                                            p                      +                      i                                        ,                                          q                      +                      j                                                        )                                            ⁢                              k                ij                                                    ,                            (                  EQ          ⁢                      xe2x80x83                    ⁢          2                )            
where the use of I denotes a series of independent calculations on each colour component as required.
FIG. 3 shows a calculation of a convolution in accordance with the finite mask 21 of FIG. 2. Each pixel 31 in an output image 32 depends upon a neighbourhood of a plurality of pixels 33 across a multitude of scan lines of an input image 34. In conventional systems, a full image semiconductor frame buffer is used to store the input image 34 in its entirety, so that there is no difficulty in accessing this neighbourhood region of pixels.
Throughout this specification, unless otherwise noted, a reference to xe2x80x9cmemoryxe2x80x9d is to be construed as a reference to high data transfer rate, preferably a low access time memory, such as semiconductor-based random access memory, which provides substantially higher data transfer rates and lower access times than, for example, a hard disc (magnetic) memory or optical disc memory. Other examples of a high data transfer rate, low access time memory include a bubble memory and mercury delay line memory, and the like.
However, the use of a frame buffer for image convolutions, amongst other image manipulation processes, poses a number of problems and disadvantages. Firstly, although the cost of such memory has dropped over the past few years, such memory remains relatively expensive. Hence, the capacity of such memory as typically used in computer systems, it is often consumed by the simultaneous execution of an operating system and one of more application programs all of which tend to use fast memory resources prior to utilizing slow memory (eg. hard disk) for intermediate storage. Further, the provision of a frame buffer encourages the rendering of graphical objects into pixel-based form thus occupying further memory resources and compounding the above noted problem.
It is therefore an object of the present invention to substantially overcome, or ameliorate, one or more difficulties associated with prior art arrangements.
The present invention provides for the use of scan line buffers (or band buffers) rather than with conventional frame buffers to perform image convolution operations, and such becomes particularly advantageous when dealing with graphical object-based images.
In accordance with one aspect of the present invention there is provided a method of applying a convolution operator to an image, the method comprising the steps of:
(a) providing a finite convolution mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;
(b) providing a buffer means adapted to store a portion of the image;
(c) rendering to the buffer means at least a predetermined number of scan lines of the image substantially equal to the number of rows or the number of columns of the convolution mask; and
(d) applying the convolution mask to the rendered plurality of scan lines to produce a scan line of an output image.
Preferably, steps (c) and (d) are repeated to produce a plurality of scan lines of the output image, wherein at the rendering step (c) a scan line is discarded and a next scan line is rendered for each scan line of the output image.
Most preferably, the image is represented in an object-based graphics environment. In such a case, the image is represented by an expression tree representation comprising a plurality of nodes. Typically the nodes are characterised as being either an operator or a primitive. Alternatively the image may be represented by an instruction sequence or by a hierarchical data representation. Generally one or more nodes of the expression tree or each instruction of the instruction sequence have associated therewith a render number. Typically the render number represents the number of scan lines to be rendered in advance of a current scan line for the node or instruction.
Preferably the coefficients of the mask are determined by an arbitrary function.
According to another aspect of the present invention there is disclosed a method of applying a convolution operator to an input image to produce an output image, the method comprising the steps of:
(a) providing to a buffer means adapted to store a portion of the image, image pixel data corresponding to at least a predetermined number of scan lines of the image; and
(b) applying a finite convolution mask to the image pixel data to produce a scan line of the output image, wherein the finite convolution mask has a plurality of coefficients arranged in a predetermined number of rows and a predetermined number of columns and the predetermined number of scan lines substantially equals at least one of the number of rows or the number of columns of the convolution mask.
According to another aspect of the present invention there is disclosed a method of applying a convolution operator to an image represented at least graphical object in an object-based graphics environment, the method comprising the steps of:
(a) providing a finite convolution mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;
(b) providing a buffer means adapted to store a portion of the image;
(c) rendering at least a predetermined number of scan lines of the at least one graphical object to the buffer means, the predetermined number of scan lines being substantially equal to the number of rows or the number of columns of the convolution mask;
(d) applying the convolution mask to the rendered plurality of scan lines to produce a scan line of an output image.
(e) repeating steps (c) and (d) to produce a plurality of scan lines of the output image, wherein at the rendering step (c) a scan line is discarded from the buffer means and a next scan line is rendered for each scan line of the output image.
According to another aspect of the present invention there is disclosed apparatus for applying a convolution operator to an image, the apparatus comprising:
first means for providing a finite convolution mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;
buffer means adapted to store a portion of the image;
second means for providing to the buffer means image pixel data of at least a predetermined number of scan lines of the input image, the predetermined number of scan lines being substantially equal to the number of rows or the number of columns of the convolution mask; and
third means for applying the convolution mask to the plurality of scan lines to produce a scan line of an output image.
Preferably, for each aspect, the buffer means is configured to retain a limited portion of the input image substantially smaller than an entirety of the input image.
The construction of an output image on a scan line basis, or optionally on a band-by-band basis with each band comprising a plurality of scan lines, is advantageous where a reduction in memory storage capacity is necessary or desirable. Similarly, it is often preferable to store only a portion of an input image, for example only a minimum number of scan lines of the input image required for performing a convolution operation, as described hereinafter.